package my.leetcode.solution;

import java.util.Arrays;
import java.util.List;

/**
 * 思路:
 */
public class P1104 {

    public static void main(String[] args) {
        System.out.println(pathInZigZagTree(14));
        System.out.println(pathInZigZagTree(10));
        System.out.println(pathInZigZagTree(1));
        System.out.println(pathInZigZagTree(26));
//        System.out.println(transform(twoPowN(10), 10, true));
//        System.out.println(transform(twoPowN(8), 8, true));
//        System.out.println(transform(twoPowN(10), 10, false));
//        System.out.println(transform(twoPowN(4), 4, false));
    }

    public static int twoPowN(int p) {
        int i = 1,n = 0;
        while(p >= i) {
            n++;
            i <<= 1;
        }
        return n;
    }

    public static int transform(int layer, int v, boolean transformIndex) {
        if((layer & 1) == 0) {
            return  (1 << layer) + (1 << (layer - 1)) - 2 - v;
        } else {
            if(transformIndex) {
                return v - 1;
            } else {
                return v + 1;
            }
        }
    }

    public static List<Integer> pathInZigZagTree(int label) {
        if(label < 1) {
            return null;
        }
        int size = twoPowN(label), s = size - 1;
        Integer[] arr = new Integer [size];
        int index = transform(size, label, true) + 1;
        while(index > 0) {
            arr[s--] = index - 1;
            index >>= 1;
        }
        arr[0] = 1;
        for(int i = 1;i < size;i++) {
            arr[i] = transform(i + 1, arr[i], false);
        }
        return Arrays.asList(arr);
    }

}
